#!/usr/bin/env python
# -*- coding:UTF-8 _*_
"""
@Project:gnn_demo-master
@File:guibing_sort.py
@IDE:PyCharm
@Author:cuixinhong
@Date:2022/4/24 16:58
"""
class Solution:
	def InversePairs(self,data):
		return self.dfs(data)%1000000007
	def dfs(self,arr):
		if len(arr)<=1:
			return 0
		big=[]
		small=[]
		res=0
		prev=arr[0]
		for i in arr[1:]:
			if i>prev:
				big.append(i)
			else:
				small.append(i)
				res+=len(big)+1
		return res+self.dfs(big)+self.dfs(small)
if __name__ == '__main__':
    nums=[1,2,3,4,5,6,7,0]
    s=Solution()
    print(s.InversePairs(nums))#7